package com.chapter1.basic.analysis;

/** 
 * @ClassName: QuickUnion 
 * @Description: quickUnion是对quickFind的一种改良
 * @author minjun minjun@bw30.com
 * @date 2015-2-13 下午2:23:05 
 *  
 */
public class QuickUnion {

	/**
	 * 所有连通分量(所有父连接)
	 */
	protected int[] array;

	/**
	 * 连通分量的数量
	 */
	protected int count;

	/**
	 * 初始化所有触点
	 */
	public QuickUnion(int count) {
		this.count = count;
		array=new int[count];
		for(int i=0;i<count;i++){
			array[i]=i;
		}
	}

	/**
	 * 
	* @Title: connected 
	* @Description: 判断是否连接 
	* @param @param m
	* @param @param n
	* @param @return    设定文件 
	* @return boolean    返回类型 
	* @throws
	 */
	public boolean connected(int m, int n) {
		return find(m) == find(n);
	}

	/**
	 * 
	* @Title: find 
	* @Description: 查找根节点
	* @param @param m
	* @param @return    设定文件 
	* @return int    返回类型 
	* @throws
	 */
	protected int find(int m) {
		
		//直到父节点为自己是，表示已经到达根节点
		while(m!=array[m]){
			m=array[m];
		}
		
		return m;
	}

	/**
	 * 
	* @Title: union 
	* @Description: 判断给定的两个数是否连通--如果不连通，则进行连通；如果已经相连，不作任何事 。
	* 相对于quickfind，优化了union方法
	* @param @param m
	* @param @param n    设定文件 
	* @return void    返回类型 
	* @throws
	 */
	public void union(int m, int n) {
		int i = find(m);
		int j = find(n);

		//若拥有相同的根节点，表示两者连通
		if (i == j) {
			return;
		}
		//否则，手动相连
		array[i]=j;
		count--;
	}
	
	public int getCount() {
		return count;
	}

	public void setCount(int count) {
		this.count = count;
	}

}
